
\subsection{前缀和}

前缀和是一种较为简单的算法，可以大大减少时间复杂度。我们可以简单理解为 “数列的前 n 项的和”。下面我们用一个例题来了解一下前缀和的主要思路。

\begin{NOTE}{例题}{}
有 N 个的正整数放到数组 A 里，现在要求一个新的数组 B，新数组的第 i 个数 B[i] 是原数组 A 第 0 到第 i 个数的和。

\end{NOTE}


对于这道题，我们有两种做法：

\begin{itemize}
\item 把对数组 A 的累加依次放入数组 B 中。
\item 递推：\texttt{B[i] = B[i-1] + A[i]} ，前提 \texttt{B[0] = A[0]}。
\end{itemize}

参考程序：

\begin{cppcode}
#include <iostream>

using namespace std;

int N, A[10000], B[10000];
int main() {
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }

  B[0] = A[0];

  for (int i = 1; i < N; i++) {
    B[i] = B[i - 1] + A[i];
  }

  for (int i = 0; i < N; i++) {
    cout << B[i] << " ";
  }

  return 0;
}
\end{cppcode}

输入：

\begin{minted}{text}
5
1 2 3 4 5
\end{minted}

输出：

\begin{minted}{text}
1 3 6 10 15 
\end{minted}

首先，\texttt{B[0] = A[0];}，前缀和数组的第一项和原数组的第一项是相等的。

\texttt{B[i] = B[i-1] + A[i]} 相信大家也能理解这个式子。意思就是：前缀和数组的第 i 项等于数组 A 的 0 到 i-1 项的和加数组 A 的第 i 项。

\subsubsection{参考}

感谢南海区青少年信息学奥林匹克内部训练教材。
